package leetcode.editor.offer;

import java.util.*;

// 剑指 Offer 38. 字符串的排列
// https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/submissions/
class ZiFuChuanDePaiLieLcof {
    public static void main(String[] args) {
        Solution solution = new ZiFuChuanDePaiLieLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String[] permutation(String s) {
            char[] array = s.toCharArray();
            Arrays.sort(array);
            backTracking(array, new boolean[s.length()]);
            return list.toArray(new String[list.size()]);
        }

        List<String> list = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        public void backTracking(char[] array, boolean[] used) {
            if (sb.length() >= array.length) {
                list.add(sb.toString());
                return;
            }

            for (int i = 0; i < array.length; i++) {
                if (i > 0 && array[i] == array[i - 1] && used[i - 1] == false) continue;
                if (used[i] == true) continue;
                sb.append(array[i]);
                used[i] = true;
                backTracking(array, used);
                used[i] = false;
                sb.deleteCharAt(sb.length() - 1);
            }
        }

        // Set去重
        /*public String[] permutation(String s) {
            dfs(s, 0, new boolean[s.length()]);
            return res.toArray(new String[res.size()]);
        }

        List<String> res = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        public void dfs(String s, int i, boolean[] used) {
            if (sb.length() == s.length()) {
                res.add(sb.toString());
                return;
            }

            Set<Character> set = new HashSet<>();

            for (int j = 0; j < s.length(); j++) {
                if (used[j] == true || set.contains(s.charAt(j))) continue;
                used[j] = true;
                set.add(s.charAt(j));
                sb.append(s.charAt(j));
                dfs(s, j + 1, used);
                sb.deleteCharAt(sb.length() - 1);
                used[j] = false;
            }
        }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
